#include <iostream>

using namespace std;
#include <vector>

//class Solution {
//public:
//    vector<int> tmp1;
//    vector<int> tmp2;
//    vector<int> index;
//
//    void merge_sort(vector<int>& nums, vector<int>& ret, int l, int r)
//    {
//        if (l >= r) return;
//
//        int mid = (l + r) >> 1;
//        merge_sort(nums, ret, l, mid);
//        merge_sort(nums, ret, mid + 1, r);
//
//        int cur1 = l, cur2 = mid + 1, i = l;
//        while (cur1 <= mid && cur2 <= r)
//        {
//            if (nums[cur1] > nums[cur2]) tmp2[i] = index[cur1], tmp1[i++] = nums[ret[index[cur1]] += r - cur2 + 1, cur1++];
//            else tmp2[i] = index[cur2], tmp1[i++] = nums[cur2++];
//        }
//        while (cur1 <= mid) tmp2[i] = index[cur1], tmp1[i++] = nums[cur1++];
//        while (cur2 <= r) tmp2[i] = index[cur2], tmp1[i++] = nums[cur2++];
//
//        for (int i = l; i <= r; i++) index[i] = tmp2[i], nums[i] = tmp1[i];
//    }
//
//    vector<int> countSmaller(vector<int>& nums) {
//        tmp1.resize(nums.size());
//        tmp2.resize(nums.size());
//        index.resize(nums.size());
//        vector<int> ret(nums.size());
//        for (int i = 0; i < nums.size(); i++) index[i] = i;
//        merge_sort(nums, ret, 0, nums.size() - 1);
//        return ret;
//    }
//};

class Solution {
public:
    vector<int> tmp;
    int Merge_Sort(vector<int>& arr, int l, int r)
    {
        if (l >= r)  return 0;

        int mid = (r + l) / 2;
        int count = Merge_Sort(arr, l, mid) + Merge_Sort(arr, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = l;
        while (cur1 <= mid && cur2 <= r)
        {
            if (arr[cur1] / 2.0 > arr[cur2]) count += r - cur2 + 1, cur1++;
            else cur2++;
        }

        cur1 = l, cur2 = mid + 1, i = l;
        while (cur1 <= mid && cur2 <= r)
        {
            if (arr[cur1] > arr[cur2]) tmp[i++] = arr[cur1++];
            else tmp[i++] = arr[cur2++];
        }
        while (cur1 <= mid) tmp[i++] = arr[cur1++];
        while (cur2 <= r) tmp[i++] = arr[cur2++];

        for (i = l; i <= r; i++)
        {
            arr[i] = tmp[i];
        }
        return count;
    }

    int reversePairs(vector<int>& arr) {
        tmp.resize(arr.size());
        int ret = Merge_Sort(arr, 0, arr.size() - 1);
        return ret;
    }
};

int main()
{
    //vector<int> nums = { 5, 2, 6, 1 };
    vector<int> nums = { 1,3,2,3,1 };
    //Solution().countSmaller(nums);
    Solution().reversePairs(nums);
    return 0;
}